'''
https://leetcode.cn/problems/path-sum-iii/description/
'''
from functools import cache
from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def cnt(root, rest):
            if not root: return 0
            rest = rest - root.val
            res = 1 if rest == 0 else 0
            res += cnt(root.left, rest) + cnt(root.right, rest)
            return res

        def pathSum(root):
            if not root: return 0
            res = cnt(root, targetSum)
            res += pathSum(root.left) + pathSum(root.right)
            return res

        return pathSum(root)
